'''
Created on May 31, 2011

Straight from the implementation suggested in cormenn.
But does not work in special cases.
[3832, 3614, 4513]
@author: anupams
'''

class QuickSort(object):

  def __init__(self):
    pass

  def swap(self, arr, fromIndex, toIndex):
    temp = arr[fromIndex]
    arr[fromIndex] = arr[toIndex]
    arr[toIndex] = temp

  def partitionArray(self, arr, left, right, pivotIndex):
    pivotVal = arr[pivotIndex]
    ## Last value to pivot index
    arr[pivotIndex] = arr[right]
    ## pivaot value to last index
    arr[right] = pivotVal
    #print " pval " + repr(pivotVal)
    leftPointer = left
    for i in range(left, right - 1):
      if arr[i] < pivotVal:
        self.swap(arr, i, leftPointer)
        leftPointer = leftPointer + 1
    self.swap(arr, leftPointer, right)
    return leftPointer


  def quickSort(self, arr, left, right):
    if right > left:
      pivotIndex = (left + right) / 2
      pivotNewIndex = self.partitionArray(arr, left, right, pivotIndex)
      #print str(pivotNewIndex -1) + '  ' + str(left) 
      #print arr
      self.quickSort(arr, left, pivotNewIndex - 1)
      #print str(pivotNewIndex + 1) + '  ' + str(right)
      #print arr
      self.quickSort(arr, pivotNewIndex + 1, right)
      

if __name__ == '__main__':
  arr = [3111, 4513, 3141, 8516, 6044, 3832, 9903, 8206, 9211, 3614]
  #arr = [3832, 3614, 4513]
  short = QuickSort()
  partitionVal = short.quickSort(arr, 0, len(arr)-1)
  print arr
